package com.zzs;

/**
 * Hello world!
 *
 */
public class App 
{
    public static final int NUM = 5;
    public static final int MAX_VALUE = -1;

    public static int row = NUM;
    public static int col = 1 << (NUM - 1);

    public static int[][] graph =
            {
                    {0, 3, MAX_VALUE, 8, 9},
                    {3, 0, 3, 10, 5},
                    {MAX_VALUE, 3, 0, 4, 3},
                    {8, 10, 4, 0, 20},
                    {9, 5, 3, 20, 0}
            };

    public static int[][] dp = new int[row][col];
    public static int[][] path = new int[row][col];

    /**
     * 旅行家问题
     * 动态规划解法
     * N个地点
     *      时间复杂度：O(N^2 * 2^N)
     *      空间复杂度：O(N * 2^N)
     */
    public static void main( String[] args ) {

        TSP();
        System.out.println("距离："+dp[0][col-1]);
        System.out.println("--- 动态数组 ---");
        printArr(dp);
        System.out.println("--- 路径数组 ---");
        printArr(path);

        getPath();

    }

    // 打印二维数组
    public static void printArr(int[][] arr){
        for (int j = 0; j < col; j++) {
            System.out.print("\t"+j);
        }
        System.out.println();
        for(int i = 0; i < row; i++) {
            System.out.print(i+":\t");
            for(int j = 0; j < col; j++) {
                System.out.print(arr[i][j]+"\t");
            }
            System.out.println();
        }
    }

    // 核心方法
    public static void TSP(){
        // 初始化第一列，值为 其他点 到 0点 的距离
        for(int i = 0;i<row; i++){
            dp[i][0] = graph[i][0];
        }
        for(int j = 1;j<col; j++){ // 从第二列开始
            for(int i = 0;i<row; i++){
                dp[i][j] = MAX_VALUE;
                if( ((j>>(i-1)) & 1) == 1){ // 集合j中的点包含点i，则无需计算
                    continue;
                }
                int temp = j; // 标记，用于提前终止循环
                for(int k = 1; k<row && temp != 0; k++){ // 找到所有可能，并计算最小值
                    temp = temp >> 1;
                    if( ((j >> (k-1)) & 1) == 0 ){
                        continue;
                    }
                    if( graph[i][k] != MAX_VALUE && dp[k][j^(1<<(k-1))] != MAX_VALUE
                            && ( dp[i][j] == MAX_VALUE || dp[i][j] > graph[i][k] + dp[k][j^(1<<(k-1))] )){
                        dp[i][j] = graph[i][k] + dp[k][ j^(1<<(k-1))];
                        path[i][j] = k;
                    }
                }
            }
        }

    }


    /**
     * 计算路径
     * 通过对 路径数组 进行分析
     */
    public static void getPath(){
        System.out.print("路径为：");
        int i = 0, j = col - 1;
        int num = path[i][j];
        System.out.print(i); // 打印终点
        while(num != 0) {
            i = num;
            j = j ^ (1 << (i - 1));
            num = path[i][j];
            System.out.print( " - "+i);
        }
        System.out.print( " - "+num);
    }

    /**
     * 计算路径
     * 通过对 动态数组 进行分析
     */
    public static void getPaht1(){

    }
}
